class OrderedDict(dict):
    """ dict that retains order of insert of keys.  del is O(N), insert should
    be O(1) (or complexity of hash insert and list append). """

    def __init__(self, values=None):
        if values is None:
            values = []
        values = list(values)
        super(OrderedDict, self).__init__(values)
        self._orderedkeys = [x[0] for x in values]

    def __setitem__(self, key, value):
        super(OrderedDict, self).__setitem__(key, value)
        self._orderedkeys.append(key)  # what about dups?

    def keys(self):
        return self._orderedkeys[:]

    def values(self):
        return [x[1] for x in self.iteritems()]

    def iterkeys(self):
        return iter(self.keys())

    def iteritems(self):
        for item in self._orderedkeys:
            yield item, self[item]

    def __delitem__(self, key):
        super(OrderedDict, self).__delitem__(key)
        del self._orderedkeys[self._orderedkeys.index(key)]


class OrderedSet(set):
    def __init__(self, itr=None):
        if itr is None:
            itr = []
        super(OrderedSet, self).__init__()
        self._order = []
        self._index = {}
        map(self.add, itr)

    def add(self, value):
        # not thread safe
        l = len(self)
        super(OrderedSet, self).add(value)
        if l < len(self):
            self._index[value] = l
            self._order.append(value)

    def index(self, value):
        if not value in self:
            return -1
        return self._index[value]

    def __iter__(self):
        return iter(self._order)
